package String.easy;

import com.sun.org.apache.xerces.internal.xs.ItemPSVI;

import java.util.Stack;

/**
 * 1.问题描述
 *      给定一个字符串 S，返回 “反转后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。
 *
 * 2.算法分析
 *     首先我们从一个具体的例子中观察：ab-ef我们需要将该字符串逆序为fe-ba,非字母字符的在逆序之后的位置与原字符串中的位置相同
 *     我们从前往后遍历字符串，如果当前为字符为字母，我们需要从后往前遍历，找到第一个字母字符，将该字符添加到新的字符串中。所以我们
 *     需要设置一个维护指针来帮助我们倒序扫描字符串，当我们找到了第一个字母字符，将该字母添加到新的字符串中，然后让j自减，重复即可
 *     这是单个指针法。
 *
 *     我们还可以利用双指针一个指向S的头，一个指向S的尾部本质思路一样只是将上述的外层的for循环改变为内外层均为while循环
 *
 *     方法三：利用栈这种数据结构的特点辅助实现字符串的遍历
 *
 *
 * 3.代码实现
 *
 *
 */
@SuppressWarnings("all")
public class 仅仅反转字母 {
    public static void main(String[] args) {
        String test = test("Test1ng-Leet=code-Q!");
        System.out.println(test);
    }

    // 单指针法
    public static String reverseOnlyLetters1(String S) {
        if(S.length() == 1 || S.length() == 0) {
            return S;
        }
        int j = S.length()-1;
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < S.length(); i++) {
            if (Character.isLetter(S.charAt(i))) {
                // 当前字符为字母字符
                // 从后往前遍历找到第一个字母字符
                while (!Character.isLetter(S.charAt(j))) {
                    j--;
                }
                // 当退出循环时说明此时的字符为字母字符
                ans.append(S.charAt(j--)); // 不懂这句代码?
            } else {
                // 当前字符不为字母字符,由于不改变非字母字符的位置，所以此时直接将当前字符添加到ans中即可
                ans.append(S.charAt(i));
            }
        }
        return ans.toString();
    }

    // 双指针法
    public static String reverseOnlyLetters2(String S) {
        StringBuilder ans = new StringBuilder();
        int i = 0;
        int j = S.length()-1;
        while (i <= S.length()-1) { // 不需要判断当前j是否大于等于0，无论如何我们都需要完整遍历S，即i的索引为S.length()-1结束
            if (Character.isLetter(S.charAt(i))) { // 当前为字母字符
                while (!Character.isLetter(S.charAt(j))) {
                    j--;
                }
                ans.append(S.charAt(j));
                j--;
            } else { // 当前为非字母字符
                ans.append(S.charAt(i));
            }
            i++; // 注意这个i++不能放在else块中，因为无论上述哪一种情况每一轮判断之后i都需要自增，所以i的自增需要放置在整个判断之外
        }
        return ans.toString();
    }


    // 辅助栈法  先进后出  不推荐 时间复杂度和空间复杂度最高，上述两种算法实现相近
    public static String test(String S) {
        Stack<Character> stack = new Stack<>(); // 定义辅助栈
        // 先将S中的字母字符全部入栈
        for (int i = 0; i < S.length(); i++) {
            if (Character.isLetter(S.charAt(i))) {
                stack.push(S.charAt(i));
            }
        }
        StringBuilder ans = new StringBuilder(); // 接受新的字符串
        // 扫描S
        for (int i = 0; i < S.length(); i++) {
            if (Character.isLetter(S.charAt(i))) { // 当前字符
                ans.append(stack.pop());
            } else { // 当前为非字符
                ans.append(S.charAt(i));
            }
        }
        return ans.toString();
    }
}
